#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

string blank(int n)
{
    return string(n, ' ');
}

string join(const vector<string>& words, int l, int r, string step)
{
    string s = words[l];
    for (int i = l + 1; i < r; i++)
        s += step + words[i];
    return s;
}

vector<string> fullJustify(const vector<string>& words, int maxWidth) {
    vector<string> res;
    int n = words.size();
    int j = 0;
    while (true)
    {
        int i = j;
        int t = 0;
        while (j < n && t + words[j].size() + j - i <= maxWidth)
            t += words[j++].size();

        if (j == n)
        {
            string s = join(words, i, n, " ");
            res.emplace_back(s + blank(maxWidth - s.size()));
            return res;
        }

        int cnt = j - i;
        int space = maxWidth - t;
        if (cnt == 1)
        {
            res.emplace_back(words[i] + blank(space));
            continue;
        }

        int avg = space / (cnt - 1);
        int extra = space % (cnt - 1);

        string s1 = join(words, i, i + extra + 1, blank(avg + 1));
        string s2 = join(words, i + extra + 1, j, blank(avg));
        res.emplace_back(s1 + blank(avg) + s2);
    }
    return res;
}

bool verifyTreeOrder(vector<int>& a) {
    int n = a.size();
    auto dfs = [&](auto&& dfs, int l, int r)->bool {
        if (l >= r)  return true;

        int i = l;
        while (a[i] < a[r])  i++;
        int m = i;
        while (a[i] > a[r])  i++;
        return i == r && dfs(dfs, l, m - 1) && dfs(dfs, m, r - 1);
    };

    return dfs(dfs, 0, n - 1);
}

int main()
{
    fullJustify({ "What","must","be","acknowledgment","shall","be" }, 16);
    return 0;
}